package com.tys.algorithm.advanced.code.class42;

import java.util.Arrays;

/**
 * 邮局选址问题
 * 一条直线上有居民点，邮局只能建在居民点上。
 * 给定一个有序正数数组arr，每个值表示居民点的一维坐标。
 * 再给定一个正数num，表示邮局的数量，
 * 选择num个居民点建立num个邮局，
 * 使所有的居民点到最近邮局的总距离最短，返回最短的总距离
 * 举例：
 * arr=[1,2,3,4,5,1000] num=2
 * 第一个邮局建立在3位置，第二个邮局建立在1000位置，
 * 那么
 * 1位置到邮局的距离为2，
 * 2位置到邮局的距离为1,3位置到邮局的距离为0,
 * 4位置到邮局的距离为1,
 * 5位置到邮局的距离为2,
 * 1000位置到邮局的距离为0，
 * 这种方案下的总距离为6，
 * 其他任何方案的总距离都不会比该方案的总距离更短，所以返回6
 */
public class Code01_PostOfficeProblem {

    //方法1：
    public static int min1(int[] arr, int num) {
        if (arr == null || num < 1 || arr.length < num) {
            return 0;
        }
        int N = arr.length;
        //多加1，减少边界讨论
        int[][] w = new int[N + 1][N + 1];
        //填w的右上半区
        for (int L = 0; L < N; L++) {
            //L==R表示一个居民点，距离0，跳过
            for (int R = L + 1; R < N; R++) {
                //之前距离：w[L][R - 1]
                //新点：arr[R]
                //之前最优邮局位置：arr[(L + R) >> 1] 中点
                w[L][R] = w[L][R - 1] + arr[R] - arr[(L + R) >> 1];
            }
        }
        //0行跳过
        int[][] dp = new int[N][num + 1];
        //第1列：0-1居民点建邮局最优，从w拿值
        for (int i = 0; i < N; i++) {
            dp[i][1] = w[0][i];
        }
        for (int i = 1; i < N; i++) {
            //邮局数不超过居民点数，邮局过剩不用求
            for (int j = 2; j <= Math.min(i, num); j++) {
                int ans = Integer.MAX_VALUE;
                for (int k = 0; k <= i; k++) {
                    //每个K划分点都出答案，取最小
                    ans = Math.min(ans, dp[k][j - 1] + w[k + 1][i]);
                }
                dp[i][j] = ans;
            }
        }
        return dp[N - 1][num];
    }

    //方法2：优化
    public static int min2(int[] arr, int num) {
        if (arr == null || num < 1 || arr.length < num) {
            return 0;
        }
        int N = arr.length;
        int[][] w = new int[N + 1][N + 1];
        for (int L = 0; L < N; L++) {
            for (int R = L + 1; R < N; R++) {
                w[L][R] = w[L][R - 1] + arr[R] - arr[(L + R) >> 1];
            }
        }
        int[][] dp = new int[N][num + 1];
        int[][] best = new int[N][num + 1];
        for (int i = 0; i < N; i++) {
            dp[i][1] = w[0][i];
            best[i][1] = -1;
        }
        for (int j = 2; j <= num; j++) {
            for (int i = N - 1; i >= j; i--) {
                int down = best[i][j - 1];
                int up = i == N - 1 ? N - 1 : best[i + 1][j];
                int ans = Integer.MAX_VALUE;
                int bestChoose = -1;
                for (int leftEnd = down; leftEnd <= up; leftEnd++) {
                    int leftCost = leftEnd == -1 ? 0 : dp[leftEnd][j - 1];
                    int rightCost = leftEnd == i ? 0 : w[leftEnd + 1][i];
                    int cur = leftCost + rightCost;
                    //<=可以，不证直接试
                    if (cur <= ans) {
                        ans = cur;
                        bestChoose = leftEnd;
                    }
                }
                dp[i][j] = ans;
                best[i][j] = bestChoose;
            }
        }
        return dp[N - 1][num];
    }

    // for test
    public static int[] randomSortedArray(int len, int range) {
        int[] arr = new int[len];
        for (int i = 0; i != len; i++) {
            arr[i] = (int) (Math.random() * range);
        }
        Arrays.sort(arr);
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int N = 30;
        int maxValue = 100;
        int testTime = 10000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int len = (int) (Math.random() * N) + 1;
            int[] arr = randomSortedArray(len, maxValue);
            int num = (int) (Math.random() * N) + 1;
            int ans1 = min1(arr, num);
            int ans2 = min2(arr, num);
            if (ans1 != ans2) {
                printArray(arr);
                System.out.println(num);
                System.out.println(ans1);
                System.out.println(ans2);
                System.out.println("Oops!");
            }
        }
        System.out.println("测试结束");

    }

}
